//给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。 
//
// （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。） 
//
// 返回 A 中好子数组的数目。 
//
// 
//
// 示例 1： 
//
// 输入：A = [1,2,1,2,3], K = 2
//输出：7
//解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
// 
//
// 示例 2： 
//
// 输入：A = [1,2,1,3,4], K = 3
//输出：3
//解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 20000 
// 1 <= A[i] <= A.length 
// 1 <= K <= A.length 
// 
// Related Topics 哈希表 双指针 Sliding Window 
// 👍 192 👎 0
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return mostDistinct(A,K) - mostDistinct(A,K - 1);
    }
    int mostDistinct(vector<int>& A,int K){
        unordered_map<int, int> map;
        int left = 0,right = 0;
        int n = A.size();
        int res = 0;
        while (right < n){
            map[A[right++]]++;
            while (map.size() > K){
                map[A[left]]--;
                if (map[A[left]] == 0)
                    map.erase(A[left]);
                left++;
            }
            res += right - left;
        }

        return res;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
